package stack;
import java.util.*;

import org.junit.Test;

import utils.ArrayGenerator;
public class Ex739 {
    class Solution {
        public int[] dailyTemperatures1(int[] T) {
            int len;
            if (T == null || (len = T.length) == 0) return new int[0];
            Stack<Integer> stack = new Stack<>();
            int[] res = new int[len];

            for (int i = len - 1; i >= 0; i--) {
                while (!stack.isEmpty() && T[stack.peek()] <= T[i]) stack.pop();
                res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
                stack.push(i);
            }
            
            return res;
        }

     
        /* 
            很有意思的解法，借鉴求next数组的做法：

            1. 从右向左遍历，最右位置肯定是0
            2. 对于中间位置i，记下个位置i + 1为next，若nums[next] > nums[i] => res[i] = next;
                否则，next更新为next + res[next], 再次比较nums[next] 与 nums[i] 的大小
                当某一时刻res[next] == 0 或者 nums[next] > nums[i] 为止，停止更新

                时间复杂度分析：
                最坏情况：首位置出现最大的数，其他位置都是从小到大，此时首位需要遍历一遍数组，而其他位置只需要查看一次后面的位置
                共遍历两趟数组
                因此时间复杂度为O(N)
        */
        public int[] dailyTemperatures(int[] T) {
            int len;
            if (T == null || (len = T.length) == 0) return new int[0];
            int[] res = new int[len];
            res[len - 1] = 0; //可以默认为0
            int next;
            loop: for (int i = len - 2; i >= 0; i--) {
                next = i + 1;
                while (T[next] <= T[i]) {
                    if (res[next] == 0) {
                        res[i] = 0;
                        continue loop;
                    }
                    next += res[next];
                }
                res[i] = next - i;
            }
            
            return res;
        }
    }
    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = {73, 74, 75, 71, 69, 72, 76, 73};
        nums = ArrayGenerator.getArray(100, 20);
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(s.dailyTemperatures(nums)));
    }
}
